package priority_queue

import "container/heap"

//参考官方文档:http://cngolib.com/container-heap.html
//优先队列的使用方法,详见测试用例

type SortType int

const (
	ASC  SortType = 1 //顺序(从小到大)
	DESC SortType = 2 //逆序(从大到小)
)

//优先队列单个元素
type Element struct {
	Value    interface{} //元素的值
	Priority int64       //元素在队列中的优先级
	Index    int         //元素在堆中的索引(元素的索引可以用于更新操作，它由heap.Interface定义的方法维护。)
}

type PriorityQueue struct {
	PriorityQueue []*Element
	SortType      SortType
}

//实现了heap.Interface接口的优先队列, 队列中包含任意多个element结构。
//type PriorityQueue []*Element

func (p *PriorityQueue) Len() int {
	return len(p.PriorityQueue)
}

func (p *PriorityQueue) Less(i, j int) bool {
	if p.SortType == ASC {
		return p.PriorityQueue[i].Priority < p.PriorityQueue[j].Priority
	} else if p.SortType == DESC {
		return p.PriorityQueue[i].Priority > p.PriorityQueue[j].Priority
	}
	//默认从小到大
	return p.PriorityQueue[i].Priority < p.PriorityQueue[j].Priority
}

func (p *PriorityQueue) Swap(i, j int) {
	p.PriorityQueue[i], p.PriorityQueue[j] = p.PriorityQueue[j], p.PriorityQueue[i]
	p.PriorityQueue[i].Index = i
	p.PriorityQueue[j].Index = j
}

//这里的push方式只是实现了heap.interface的接口
func (p *PriorityQueue) Push(x interface{}) {
	n := len(p.PriorityQueue)
	element := x.(*Element)
	element.Index = n
	p.PriorityQueue = append(p.PriorityQueue, element)
}

//这里的Pop方式只是实现了heap.interface的接口
func (p *PriorityQueue) Pop() interface{} {
	//得到优先队列的长度
	n := len(p.PriorityQueue)
	//得到优先队列的最后一个元素
	element := p.PriorityQueue[n-1]
	//设置元素的下标为-1
	element.Index = -1
	//删除优先队列的最后一个元素
	p.PriorityQueue = p.PriorityQueue[0 : n-1]
	return element
}

//新建优先队列
func NewPriorityQueue(sortType SortType) *PriorityQueue {
	//新建优先队列
	priorityQueue := &PriorityQueue{
		PriorityQueue: make([]*Element, 0),
		SortType:      sortType,
	}
	//初始化优先队列
	heap.Init(priorityQueue)
	return priorityQueue
}

//入队
func (p *PriorityQueue) EnterQueue(element *Element) {
	heap.Push(p, element)
}

//出队
func (p *PriorityQueue) OutQueue() *Element {
	//判断队列元素个数
	if 0 == len(p.PriorityQueue) {
		return nil
	}
	return heap.Pop(p).(*Element)
}

//删除元素
func (p *PriorityQueue) DeleteElement(index int) *Element {
	length := len(p.PriorityQueue)
	if 0 == length || index < 0 || index >= length {
		return nil
	}
	//移除指定下标的元素
	return heap.Remove(p, index).(*Element)
}

//修改队列中指定元素的Value和Priority。
func (p *PriorityQueue) FixElement(element *Element, value interface{}, priority int64) {
	element.Value = value
	element.Priority = priority
	heap.Fix(p, element.Index)
}
